//寻找旋转排序数组中的最小值
class Solution {
public:
    int findMin(vector<int>& nums) 
    {
        // [1 2 3 4 5 6 7]
        // [7],[1,2,3,4,5,6]
        // [5,6,7],[1,2,3,4]
        // [3,4,5,6,7],[1,2]
        //可以发现不管怎么旋转 一定是一个或两个的上升区间
        // 那就可以跟区间的末端点进行比较
        //if(nums[mid]> nums[n-1]) 一定在右区间
        int  l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(nums[mid]>nums[nums.size()-1]) l=mid+1;
            else r=mid;
        }
        return nums[l];
    }
};
//寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) 
    {
        // if(nums.size()==1) return 0;
        // else if(nums.size()==2) return nums[0]>nums[1]?0:1;

        int l=0,r=nums.size()-1;
        while(l<r)
        {
            // 1 2 3 2 3 4 5 6 7 2
            int mid=(l+r)/2;
            //如果中间两个成上升趋势 右边一定有峰值 因为nums[n]=负无穷
            if(nums[mid]<nums[mid+1]) l=mid+1;
            else r=mid;
        }
        return l;
    }
};
//山脉数组的峰顶索引

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        // 1 2 3 4 5 4 1
        //返回5的下标
        //找到mid  如果 arr[mid]<arr[mid+1] 说明i一定在右侧
        //如果arr[mid] > arr[mid+1] i一定在左侧 但包括mid
        int l=0,r=arr.size()-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(arr[mid] < arr[mid+1]) l=mid+1;
            else r=mid;
        } 
        return l;
    }
};
//搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        //找一个值 用朴素的
        int l=0,r=nums.size()-1;
        int mid=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(nums[mid]>target) r=mid-1;
            else if(nums[mid] <target) l=mid+1;
            else return mid;
        }
        if(nums[mid] > target) return mid;
        else return mid+1;
    }
};